package sort;

public class PaiXu {

    public static void main(String[] args) {
        int[] array = {6, 7, 9, 8, 4, 5, 2, 1, 3};
//        maopao(array);
//        xuanze(array);
//        charu(array);
        kuaisu(array);
        for (int value : array) {
            System.out.println(value);
        }
    }

    // 冒泡排序
    public static void maopao(int[] array) {
        // 当前数组的长度
        int arrLength = array.length - 1;
        int len;
        for (len = arrLength; len >= 0; len--) {
            for (int i = 0; i < len; i++) {
                if (array[i] > array[i + 1]) {
                    int swap = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = swap;
                }
            }
        }
    }

    public static void xuanze(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int minIndex = i; // 最小值的位置
            for (int j = i; j < array.length - 1; j++) {
                if (array[j + 1] < array[minIndex]) {
                    minIndex = j + 1;
                }
            }
            // 里面循环结束 说明找到最小项
            if (minIndex != i) {
                int swap = array[minIndex];
                array[minIndex] = array[i];
                array[i] = swap;
            }
        }
    }

    public static void charu(int[] array) {
        int len = array.length;
        for (int i = 1; i < len; i++) {
            for (int j = i; j > 0; j--) {
                if (array[j] < array[j - 1]) {
                    int temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                }
            }
        }
    }

    // 快速排序
    public static void kuaisu(int[] array) {
        sort(array, 0, array.length - 1);
    }

    private static void sort(int[] array, int low, int high) {
        int i, j, index;
        if (low > high) {
            return;
        }
        i = low; // 哨兵i
        j = high; // 哨兵j
        index = array[i]; // 第一次排序的基准数
        while (i < j) { // 从表的俩端往中间开始扫描
            while (i < j && array[j] >= index)
                j--;
            if (i < j)
                array[i++] = array[j];
            while (i < j && array[i] < index)
                i++;
            if (i < j)
                array[j--] = array[i];
        }
        array[i] = index;
        sort(array, low, i - 1);
        sort(array, i + 1, high);
    }
}
